/// @tags: Matrix Recursion DP Count
#include <cstdio>
#include <cstring>
#include <iostream>

using namespace std;

namespace BlueQuantum {

typedef long long ll;

int const mod = 1e9 + 7;

struct Matrix {
  int a[5][5];

  Matrix() { memset(a, 0, sizeof(a)); }

  inline Matrix operator*(Matrix const& rhs) const {
    Matrix res;
    for (int i = 0; i < 5; ++i)
      for (int k = 0; k < 5; ++k)
        for (int j = 0; j < 5; ++j)
          res.a[i][j] = (res.a[i][j] + (ll)a[i][k] * rhs.a[k][j] % mod) % mod;
    return res;
  }

  inline Matrix operator^(int exp) {
    Matrix res;
    for (int i = 0; i < 5; ++i) res.a[i][i] = 1;
    while (exp) {
      if (exp & 1) res = res * *this;
      *this = *this * *this;
      exp >>= 1;
    }
    return res;
  }
};

inline int main() {
  int t;
  cin >> t;
  for (int n; t; --t) {
    Matrix T;
    T.a[0][1] = T.a[1][0] = T.a[1][1] = T.a[2][3] = 1;
    T.a[3][1] = 2, T.a[3][2] = T.a[3][3] = 1;
    T.a[4][1] = mod - 1, T.a[4][4] = 1;
    cin >> n;
    if (n < 3) cout << "0\n";
    else {
      Matrix A;
      A.a[0][2] = 1, A.a[0][3] = A.a[0][4] = 2;
      cout << (A * (T ^ (n - 2))).a[0][1] << '\n';
    }
  }
  return 0;
}

}  // namespace BlueQuantum

int main() {
#ifndef ONLINE_JUDGE
#ifdef LOCAL
  freopen("/tmp/CodeTmp/testdata.in", "r", stdin);
  freopen("/tmp/CodeTmp/testdata.out", "w", stdout);
#else
  freopen("GZOI2019] 逼死强迫症.in", "r", stdin);
  freopen("GZOI2019] 逼死强迫症.out", "w", stdout);
#endif
#endif

  ios::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
  return BlueQuantum::main();
}
